//? 1. 循环比较每个位置左为0右为1的需要翻转的情况 取最小

//? 2. 动态规划
//如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
//
// 给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
//
// 返回使 s 单调递增的最小翻转次数。
//
//
//
// 示例 1：
//
//
//输入：s = "00110"
//输出：1
//解释：翻转最后一位得到 00111.
//
//
// 示例 2：
//
//
//输入：s = "010110"
//输出：2
//解释：翻转得到 011111，或者是 000111。
//
//
// 示例 3：
//
//
//输入：s = "00011000"
//输出：2
//解释：翻转得到 00000000。
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁵
// s[i] 为 '0' 或 '1'
//
//
// Related Topics 字符串 动态规划 👍 325 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function minFlipsMonoIncr(s: string): number {
    const n = s.length;
    let dp0 = 0, dp1 = 0;
    for (let i = 0; i < n; i++) {
        const c = s[i];
        //? dp1New = Math.min(dp0, dp1)是需要根据前面1转0和0转1更小那个决定的，因为1前面是0或是1都是可以的
        //? 而dp0New无需最小值比较是因为0的前面一定是0而不可能是1
        let dp0New = dp0, dp1New = Math.min(dp0, dp1);
        if (c === '1') {
            //? 1->0次数
            dp0New++;
        } else {
            //? 0->1次数
            dp1New++;
        }
        dp0 = dp0New;
        dp1 = dp1New;
    }
    return Math.min(dp0, dp1);
};
//leetcode submit region end(Prohibit modification and deletion)
